// 有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满
// 对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子
// 如果不存在每个袋子都装满的方案返回-1
public class AppleMinBags {
    public static int bag1(int apple){
        int ans = f(apple);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int f(int fest){ //参数为剩余苹果的数量
        if(fest < 0) {
            return Integer.MAX_VALUE;
        }

        if(fest == 0){
            return 0;
        }
        //使用8规格的袋子，装苹果
        int p1 = f(fest - 8);
        //使用6规格的袋子，装苹果
        int p2 = f(fest - 6);
        p1 += p1 == Integer.MAX_VALUE ? 0 : 1;
        p2 += p2 == Integer.MAX_VALUE ? 0 : 1;

        return Math.min(p1,p2);
    }

    public static void main(String[] args) {
        //列出0~100个苹果的所有情况，然后寻找规律
        for(int apple = 0; apple <= 100; apple++){
            System.out.println("apple: " + apple + ", bags: "+ bag1(apple) );
        }
    }

    //根据规律找到最优解
    public static int bag2(int apple){
        if((apple & 1) != 0){  //奇数个苹果无法装满袋子
            return -1;
        }

        if(apple < 18){
            if(apple == 0){
                return 0;
            }
            else if(apple == 6 || apple ==8){
                return 1;
            } else if(apple == 12 || apple == 14 || apple == 16){
                return 2;
            }else {
                return -1;
            }
        }else{
            return (apple - 18) / 8 + 3;
        }
    }
}
